package charactor

import (
	"fmt"
	"math"
	"regexp"
	"sort"
	"strconv"
	"strings"
)

//最长公共前缀
//编写一个函数来查找字符串数组中的最长公共前缀。
//
//如果不存在公共前缀，返回空字符串 ""。
//输入：strs = ["flower","flow","flight"]
//输出："fl"
func longestCommonPrefix(strs []string) string {
	maxPrefix := ""
	for i := 0; i < len(strs); i++ {
		ok := strings.HasPrefix(strs[i], maxPrefix)
		if ok {
			if i == 0 {
				maxPrefix = strs[0]
			}
		} else {
			maxPrefix = maxPrefix[:len(maxPrefix)-1]
			for !strings.HasPrefix(strs[i], maxPrefix) {
				maxPrefix = maxPrefix[:len(maxPrefix)-1]
			}
		}
	}
	return maxPrefix

}

//编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
//
//不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
func reverseString(s []byte) {
	h := 0
	l := len(s) - 1
	for h < l {
		tmp := s[l]
		s[l] = s[h]
		s[h] = tmp
		h++
		l--
	}
}

/**
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。
*/
func reverse(x int) int {
	positiveNum := false
	if x < 0 {
		x *= -1
		positiveNum = true
	}
	//巧妙使用%和/  计算
	tmp := 0
	last := 0
	for x > 0 {
		last = x % 10
		x /= 10
		tmp = tmp*10 + last
		if tmp > math.MaxInt32 {
			return 0
		}
	}
	if positiveNum {
		tmp *= -1
	}
	return tmp
}

/**
字符串中的第一个唯一字符
给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
输入: s = "leetcode"
输出: 0

方式1： 数组模拟map
方式2：map存储计数
*/
func firstUniqChar(s string) int {
	countMap := [26]int{}
	//用数组模拟 map 记录字符出现次数
	for _, char := range s {
		countMap[char-'a'] += 1
	}
	for i := range s {
		if countMap[s[i]-'a'] == 1 {
			return i
		}
	}
	return -1
}

/**
有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若s 和 t中每个字符出现的次数都相同，则称s 和 t互为字母异位词。

解法1：排序，然后比较字符
解法2：map记录每个字符的次数 遍历另一个字符串的时候对应字符次数减少


作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn96us/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func isAnagram(s string, t string) bool {
	if len(s) != len(t) {
		return false
	}
	countMap := [26]int{}
	count := 0 //用来记录字符数是否一致 =0 说明一致
	//用数组模拟 map 记录字符出现次数
	for i := 0; i < len(s); i++ {
		countMap[s[i]-'a']++
		//将s中的字符加进去 统计出现次数，count 记录出现的字符数
		if countMap[s[i]-'a'] == 1 {
			count++
		}
		//将t中的字符加进去 如果如果字符出现次数一致(增加多少次，就会减去多少次)，则count -1
		countMap[t[i]-'a']--
		if countMap[t[i]-'a'] == 0 {
			count--
		}
	}
	if count == 0 {
		return true
	}
	return false
}

//使用排序的方式来判断是否是异位串
func isAnagramWithSort(s string, t string) bool {

	sb := []byte(s)
	tb := []byte(t)
	sort.Slice(sb, func(i, j int) bool {
		if s[i] < s[j] {
			return true
		}
		return false
	})
	sort.Slice(tb, func(i, j int) bool {
		if s[i] < s[j] {
			return true
		}
		return false
	})
	if string(sb) == string(tb) {
		return true
	}
	return false
}

/**
验证回文串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。
输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串
*/
func isPalindrome(s string) bool {
	compile, _ := regexp.Compile("[^0-9a-zA-Z]+")
	replaceAllString := compile.ReplaceAllString(s, "")
	cleanStr := strings.ToLower(replaceAllString)
	start := 0
	end := len(cleanStr) - 1
	for start <= end {
		if cleanStr[start] != cleanStr[end] {
			return false
		}
		start++
		end--
	}
	return true
}

/**
字符串转换整数 (atoi)
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意：

本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnoilh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
func myAtoi(s string) int {
	noPrefixSpace := strings.TrimLeft(s, " ")
	var number []byte
	negative := false
	flag := false
	//找出数字
	for i := 0; i < len(noPrefixSpace); i++ {
		if (noPrefixSpace[i] == '-' || noPrefixSpace[i] == '+') && !flag {
			if noPrefixSpace[i] == '-' {
				negative = true
			}
			flag = true
			continue
		}
		if noPrefixSpace[i] >= '0' && noPrefixSpace[i] <= '9' {
			flag = true
			number = append(number, noPrefixSpace[i])
			continue
		}
		break
	}
	//转换数字
	result := int32(0)
	for i := range number {

		temp := result*10 + int32(number[i]-'0')
		// 越界后，数值和期望数值发生变化，取余再除10获取原始值，比对判断
		if temp/10 != result {
			if !negative {
				return math.MaxInt32
			} else {
				return math.MinInt32
			}
		}
		result = temp
	}
	if negative {
		result *= -1
	}
	return int(result)
}

/**
括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。



示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
*/
func generateParenthesis(n int) []string {
	var result []string
	var generateFunc func(left, right int, item string)
	generateFunc = func(leftNum, rightNum int, item string) {
		if leftNum == 0 && rightNum == 0 {
			//括号都用完了，拼接结果
			result = append(result, item)
		}
		if leftNum < 0 || rightNum < 0 || leftNum > rightNum {
			//左右括号都用完了，左括号数 一定<=右括号数 否则是错误的括号使用
			return
		}
		generateFunc(leftNum-1, rightNum, item+"(")
		generateFunc(leftNum, rightNum-1, item+")")
	}
	generateFunc(n, n, "")
	return result
}

//使用动态规划来生成括号
func generateParenthesisWithDynamic(n int) []string {
	var innerDpFunc func(n int) map[int][]string
	innerDpFunc = func(n int) map[int][]string {
		if n == 0 {
			return map[int][]string{0: {""}}
		}
		if n == 1 {
			return map[int][]string{0: {""}, 1: {"()"}}
		}
		lastMap := innerDpFunc(n - 1)
		var oneRes []string
		for i := 0; i < n; i++ {
			inners := lastMap[i]
			outers := lastMap[n-1-i]
			for _, inner := range inners {
				for _, outer := range outers {
					oneRes = append(oneRes, "("+inner+")"+outer)
				}
			}
		}
		lastMap[n] = oneRes
		return lastMap
	}
	return innerDpFunc(n)[n]
}

func myPow(x float64, n int) float64 {
	if x == 0 {
		return 1
	}
	base := x
	negetive := false
	if n < 0 {
		negetive = true
		n *= -1
	}
	for i := 0; i < n-1; i++ {
		x *= base
	}
	if negetive {
		//n<0 负冥数
		x = 1 / x
	}
	return x
}

//查看 指定字符串是否可以用wordlist中的单词组成
func wordBWithDfs(s string, wordList []string) bool {
	var ifunc func(s string, wordDict map[string]bool) bool
	ifunc = func(s string, wordDict map[string]bool) bool {
		if len(s) == 0 {
			return true
		}
		for i := 0; i <= len(s); i++ {
			prefix := s[:i]
			_, ok := wordDict[prefix]
			if ok && ifunc(s[i:], wordDict) {
				return true
			}
		}
		return false
	}
	wordDict := make(map[string]bool)
	for _, v := range wordList {
		wordDict[v] = true
	}
	return ifunc(s, wordDict)
}

/**
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func exist(board [][]byte, word string) bool {

	var visited [][]bool
	//初始化visited
	for i := 0; i < len(board); i++ {
		tmp := make([]bool, len(board[i]))
		visited = append(visited, tmp)
	}
	//
	var check func(board [][]byte, visited [][]bool, row int, col int, section string) bool
	check = func(board [][]byte, visited [][]bool, row int, col int, section string) bool {
		if !strings.HasPrefix(word, section) {
			return false
		} //剪枝
		if len(section) >= len(word) {
			//长度相等 则找到了
			return true
		}
		visited[row][col] = true
		directionMap := [][]int{{0, 1}, {0, -1}, {-1, 0}, {1, 0}} //四个方向移动
		defer func() { visited[row][col] = false }()
		for _, dir := range directionMap {
			newRow, newCol := dir[0]+row, dir[1]+col
			//判断边界
			if newRow < 0 || newRow >= len(board) || newCol < 0 || newCol >= len(board[newRow]) {
				continue
			}
			if visited[newRow][newCol] {
				continue
			}
			if check(board, visited, newRow, newCol, fmt.Sprintf("%v%v", section, string(board[newRow][newCol]))) {

				return true
			}
		}
		return false
	}
	for i := 0; i < len(board); i++ {
		for k := 0; k < len(board[i]); k++ {
			//每个位置都可能成为起始点，所有都要试一试，有结果就直接返回
			if check(board, visited, i, k, string(board[i][k])) {
				return true
			}
		}
	}

	return false
}

/**
13. 罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。
示例 1:

输入: s = "III"
输出: 3
*/
func romanToInt(s string) (ans int) {
	//定义转义map
	symbolValues := map[byte]int{'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}

	n := len(s)
	for i := range s {
		value := symbolValues[s[i]]
		if i < n-1 && value < symbolValues[s[i+1]] {
			//当小值在大值的左边，则减小值，如 IV=5-1=4；
			ans -= value
		} else {
			//当小值在大值的右边，则加小值，如 VI=5+1=6；
			//罗马数字由 I,V,X,L,C,D,M 构成；
			//由上可知，右值永远为正，因此最后一位必然为正。
			ans += value
		}
	}
	return
}

/**
电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
*/
func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	//组合
	var seqFunc func(tmpList []string, target string) []string
	seqFunc = func(tmpList []string, target string) []string {
		var result []string
		for i := range target {
			ch := string(target[i])
			for i2 := range tmpList {
				result = append(result, tmpList[i2]+ch)
			}
		}
		return result
	}
	//
	result := []string{""}
	board := []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
	for i := range digits {
		index, _ := strconv.Atoi(string(digits[i]))
		result = seqFunc(result, board[index])
	}
	return result
}

/**
最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
*/
func longestCommonSubsequence(text1 string, text2 string) int {
	m, n := len(text1), len(text2)
	dp := make([][]int, m+1)
	for i := 0; i < m+1; i++ {
		dp[i] = make([]int, n+1)
	}
	//计算 i-j位置的最长字串 ace| aedda
	for i := range text1 {
		for j := range text2 {
			if text1[i] == text2[j] {
				dp[i+1][j+1] = dp[i][j] + 1 //i j 相等，则i+1位置的相同前缀+1
			} else {
				dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]) //因为 i，j 位置时2个字符串在 前缀长度不一样，所以要取2组的最长前缀max
			}
		}
	}
	return dp[m][n] //到【m+1】【n+1】的最长公共字串
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

/**
单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-break
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func wordBreak(s string, wordDict []string) bool {
	//利用全排列思想  回溯法+剪枝
	result := false
	var internalFun func(s string, index int, wordDict []string)
	internalFun = func(s string, index int, wordDict []string) {
		if index >= len(wordDict) {
			//判断结果
			if strings.Join(wordDict, "") == s {
				result = true
			}
		}
		for i := index; i < len(wordDict); i++ {
			swap(i, index, wordDict)
			//剪枝
			if !strings.HasPrefix(s, wordDict[0]) {
				swap(i, index, wordDict) //交换回来 避免造成子问题污染
				continue
			} else {
				internalFun(s, index+1, wordDict)
				swap(i, index, wordDict) //交换回来 避免造成子问题污染
			}
		}
	}
	internalFun(s, 0, wordDict)
	return result
}
func swap(ia, ib int, arr []string) {
	tmp := arr[ia]
	arr[ia] = arr[ib]
	arr[ib] = tmp
}
